package SwordFingerOffer;

public class Q47_GiftMazValue {
    //礼物最大价值
    //向右向下 ==> 拿到最大价值
    //==> 既然规定了方向，就不需要在循环里进行递归了
    public int maxValue(int[][] grid) {
       if (grid == null)
           return 0;
       return process(grid, 0, 0);
    }

    //返回最大价值
    public int process(int[][] grid, int row, int col) {

        //越界
        if (row == grid.length - 1 && col == grid[0].length - 1) {
            return grid[row][col];
        }
        //携带当前价值走向终点
//        curValue += grid[row][col];
        int valueDown = 0;
        int valueRight = 0;
        //向右
        if (col + 1 != grid[0].length)
            valueRight = process(grid, row, col + 1);
        //向下
        if (row + 1 != grid.length)
            valueDown = process(grid, row + 1, col);

        return Math.max(valueDown, valueRight) + grid[row][col];
    }

    //动态规划版
    //行列尝试模型的 dp
    public int maxValueDP(int[][] grid){
        int M = grid.length - 1;
        int N = grid[0].length - 1;
        int[][] dp = new int[M + 1][N + 1];
        dp[M][N] = grid[M][N];
        //最后一行填充
        for (int i = N - 1; i >= 0 ; i--) {
            dp[M][i] = grid[M][i] + dp[M][i + 1];
        }
        //最后一列填充
        for (int i = M - 1; i >= 0 ; i--) {
            dp[i][N] = grid[i][N] + dp[i + 1][N];
        }
        //循环递推
        for (int i = M - 1; i >= 0 ; i--) {
            for (int j = N - 1; j >= 0 ; j--) {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j + 1]) + grid[i][j];
            }
        }

        return dp[0][0];
    }

    public static void main(String[] args) {
        Q47_GiftMazValue fun = new Q47_GiftMazValue();
        System.out.println(fun.maxValueDP(new int[][]{{1, 2, 5}, {3, 2, 1}}));
    }

}